Mini parser¶
Time: O(N); Space: O(H); medium
Note:
H is the depth of the recursion
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Example 1:
Input: s = “324”
Output: 324
Explanation:
You should return a NestedInteger object which contains a single integer 324.
Example 2:
Input: s = “[123,[456,[789]]]”
Output: a NestedInteger object containing a nested list with 2 elements:
Explanation:
An integer containing value 123.
A nested list containing two elements:
An integer containing value 456.
A nested list with one element:
2.2.1. An integer containing value 789.
Constraints:
String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].
1. Basic Ideas [Stack]¶
Whenever we found ‘[’, DO NOT push.
We initialize a empty NestedInteger as place holder
Whenever we found ‘]’, we combine the last 2 place holers
Whenever we found digits/‘-’, look ahead to get what we need.
Then construct NestedInteger, then combine it into last place holder
[38]:
"""
This is the interface that allows for creating nested lists.
You should not implement it, or speculate about its implementation
"""
class NestedInteger(object):
def __init__(self, value=None):
"""
If value is not specified, initializes an empty list.
Otherwise initializes a single integer equal to value.
"""
if not value:
self.list = []
else:
self.val = value
def isInteger(self):
"""
Return True if this NestedInteger holds a single integer, rather than a nested list.
:rtype: bool
"""
return self.val is not None
def add(self, elem):
"""
Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
:rtype: none
"""
if self.list is not None:
self.list.append(elem)
else:
self.list = []
self.list.append(elemm)
def setInteger(self, value):
"""
Set this NestedInteger to hold a single integer equal to value.
:rtype: void
"""
self.val = value
def getInteger(self):
"""
Return the single integer that this NestedInteger holds, if it holds a single integer
Return None if this NestedInteger holds a nested list
:rtype: none
"""
return self.val
def getList(self):
"""
Return the nested list that this NestedInteger holds, if it holds a nested list
Return None if this NestedInteger holds a single integer
:rtype: List[NestedInteger]
"""
return self.list
[39]:
class Solution1(object):
def deserialize(self, s: str) -> NestedInteger:
"""
:type s: str
:rtype: NestedInteger
"""
if not s:
return NestedInteger()
if s[0] != '[':
return NestedInteger(int(s))
stack = []
i = 0
for j in range(len(s)):
if s[j] == '[':
# If encounters '[', push current NestedInteger to stack and start a new one.
stack += NestedInteger(),
i = j+1
elif s[j] in ',]':
# If encounters ',', append a new number to curr NestedInteger, if this comma is not right after a brackets.
if s[j-1].isdigit():
stack[-1].add(NestedInteger(int(s[i:j])))
if s[j] == ']' and len(stack) > 1:
# If encounters ']', end current NestedInteger and pop a NestedInteger from stack to continue.
cur = stack[-1]
stack.pop();
stack[-1].add(cur)
i = j+1
return stack[-1]
[40]:
sol = Solution1()
s = "324"
res = sol.deserialize(s)
assert res.val == 324
s = "[123,[456,[789]]]"
res = sol.deserialize(s)